/*
Author:jfwang213
*/
/*
According to Introduction to Algorithms
*/
#include "red_black_tree.h"
#include "stdlib.h"
#include "stdio.h"

rb_tree* init_rb_tree()
{
	rb_tree *res = (rb_tree*)malloc(sizeof(rb_tree));
	res->nil->color = BLACK;
	res->nil->left = res->nil->right = NULL;
	res->root = res->nil;
	return res;
}

rb_node *rotate_left(rb_tree* tree,rb_node *father)
{
	rb_node *right_son = father->right;
	rb_node *grand = father->parent;
	rb_node *sonson = right_son->left;
	right_son->parent = father->parent;
	father->right = right_son->left;
	right_son->left = father;
	father->parent = right_son;
	if (grand != tree->nil)
	{
		if (grand->left == father)
		{
			grand->left = right_son;
		}
		else
		{
			grand->right = right_son;
		}
	}
	if (sonson != tree->nil)
	{
		sonson->parent = father;
	}
	if (tree->root == father)
	{
		tree->root = right_son;
	}
	return right_son;
}
rb_node * rotate_right(rb_tree* tree,rb_node *father)
{
	rb_node *left_son = father->left;
	rb_node *grand = father->parent;
	rb_node *sonson = left_son->right;
	left_son->parent = father->parent;
	father->left = left_son->right;
	left_son->right = father;
	father->parent = left_son;
	if (grand != tree->nil)
	{
		if (grand->left == father)
		{
			grand->left = left_son;
		}
		else
		{
			grand->right = left_son;
		}
	}
	if (sonson != tree->nil)
	{
		sonson->parent = father;
	}
	if (tree->root == father)
	{
		tree->root = left_son;
	}
	return left_son;
}

void rb_insert_fix_up(rb_tree *tree,rb_node *node)
{
	rb_node *parent = node->parent;
	rb_node *grand,*uncle;
	while (RED == parent->color)
	{
		grand = parent->parent;
		if (parent == grand->left)
		{
			uncle = grand->right;
		}
		else
		{
			uncle = grand->left;
		}
		if (RED == uncle->color)
		{
			//case 1
			uncle->color = parent->color = BLACK;
			grand->color = RED;
			node = grand;
			parent = node->parent;
		}
		else
		{
			if (uncle == grand->right)
			{
				if ( node == parent->right)
				{
					//case 2
					parent = rotate_left(tree,parent);
					node = parent->left;
				}
				//case 3
				grand->color = RED;
				parent->color = BLACK;
				rotate_right(tree,grand);
			}
			else
			{
				if (node == parent->left)
				{
					//case 2
					parent = rotate_right(tree,parent);
					node = parent->right;
				}
				//case 3
				grand->color = RED;
				parent->color = BLACK;
				rotate_left(tree,grand);
			}
		}
	}
	tree->root->color = BLACK;
}

void rb_insert(rb_tree *tree,int key)
{
	rb_node *new_node = (rb_node*)malloc(sizeof(rb_node));
	new_node->left = new_node->right = tree->nil;
	new_node->key = key;
	if (tree->root == tree->nil)
	{
		tree->root = new_node;
		new_node->parent = tree->nil;
		new_node->color = BLACK;
	}
	else
	{
		rb_node *son,*father;
		char fine_same = 0;
		son = tree->root;
		while (son!=tree->nil)
		{
			father = son;
			if (key<son->key)
			{
				son = son->left;
			}
			else if (key > son->key)
			{
				son = son->right;
			}
			else
			{
				fine_same = 1;
				break;
			}
		}
		if (0 == fine_same)
		{
			if (key<father->key)
			{
				father->left = new_node;
			}
			else
			{
				father->right = new_node;
			}
			new_node->parent = father;
			new_node->color = RED;
			rb_insert_fix_up(tree,new_node);
		}
	}
}

rb_node* rb_search(rb_tree *tree,int key)
{
	rb_node *node = tree->root;
	while (node != tree->nil)
	{
		if (node->key < key)
		{
			node = node->right;
		}
		else if (node->key > key)
		{
			node = node->left;
		}
		else
		{
			return node;
		}
	}
	return NULL;
}

rb_node *rb_min(rb_tree *tree,rb_node *node)
{
	while (node->left != tree->nil)
	{
		node = node->left;
	}
	return node;
}

rb_node *rb_successor(rb_tree *tree,rb_node *node)
{
	if (node->right != tree->nil)
	{
		return rb_min(tree,node->right);
	}
	else if(node != tree->root)
	{
		rb_node *parent = node->parent;
		while (parent != tree->nil && parent->right == node)
		{
			node = parent;
			parent = node->parent;
		}
		return node;
	}
	return NULL;
}

void rb_delete_fix_up(rb_tree *tree,rb_node *node)
{
	rb_node *parent = node->parent;
	rb_node *sibling;
	while (node != tree->root && BLACK == node->color)
	{
		parent = node->parent;
		if (node == parent->left)
		{
			sibling = parent->right;
			if (RED == sibling->color)
			{
				parent->color = RED;
				sibling->color = BLACK;
				parent = rotate_left(tree,parent);
				parent = parent->left;
				sibling = parent->right;
			}
			if (BLACK == sibling->left->color && BLACK == sibling->right->color)
			{
				sibling->color = RED;
				node = parent;
			}
			else 
			{
				if (BLACK == sibling->right->color)
				{
					sibling->color = RED;
					sibling->left->color = BLACK;
					sibling = rotate_right(tree,sibling);
				}
				sibling->color = parent->color;
				sibling->right->color = BLACK;
				parent->color = BLACK;
				rotate_left(tree,parent);
				node = tree->root;
			}
		}
		else
		{
			sibling = parent->left;
			if (RED == sibling->color)
			{
				parent->color = RED;
				sibling->color = BLACK;
				parent = rotate_right(tree,parent);
				parent = parent->right;
				sibling = parent->left;
			}
			if (BLACK == sibling->left->color && BLACK == sibling->right->color)
			{
				sibling->color = RED;
				node = parent;
			}
			else 
			{
				if (BLACK == sibling->left->color)
				{
					sibling->color = RED;
					sibling->right->color = BLACK;
					sibling = rotate_left(tree,sibling);
				}
				sibling->color = parent->color;
				sibling->left->color = BLACK;
				parent->color = BLACK;
				rotate_right(tree,parent);
				node = tree->root;
			}
		}
	}
	node->color = BLACK;
}

void rb_delete(rb_tree *tree,int key)
{
	rb_node *node = rb_search(tree,key);
	rb_node *to_delete;
	rb_node *parent,*son;
	if (NULL == node)
	{
		return;
	}
	if (node->left == tree->nil || node->right == tree->nil)
	{
		to_delete = node;
	}
	else
	{
		to_delete = rb_successor(tree,node);
	}
	parent = to_delete->parent;
	if (to_delete->left != tree->nil)
	{
		son = to_delete->left;
	}
	else
	{
		son = to_delete->right;
	}
	if (parent != tree->nil)
	{
		if (parent->left == to_delete)
		{
			parent->left = son;
		}
		else
		{
			parent->right = son;
		}
	}
	son->parent = parent;
	if (node != to_delete)
	{
		node->key = to_delete->key;
	}
	if (to_delete == tree->root)
	{
		tree->root = son;
	}
	if (to_delete->color == BLACK)
	{
		rb_delete_fix_up(tree,son);
	}
}

void preorder(rb_tree* tree,rb_node *node)
{
	if (node == tree->nil)
	{
		return;
	}
	printf("%d",node->key);
	if (BLACK == node->color)
	{
		printf("B ");
	}
	else
	{
		printf("R ");
	}
	preorder(tree,node->left);
	preorder(tree,node->right);
}

void rb_preorder(rb_tree* tree)
{
	preorder(tree,tree->root);
	printf("\n");
}

void inorder(rb_tree *tree,rb_node *node)
{
	if (node == tree->nil)
	{
		return;
	}
	inorder(tree,node->left);
	printf("%d",node->key);
	if (BLACK == node->color)
	{
		printf("B ");
	}
	else
	{
		printf("R ");
	}
	inorder(tree,node->right);
}
void rb_inorder(rb_tree *tree)
{
	inorder(tree,tree->root);
	printf("\n");
}

char check_node(rb_tree *tree,rb_node *node,int depth)
{
	if (RED == node->color && (node->left->color != BLACK || node->right->color != BLACK))
	{
		return 0;
	}
	if (node == tree->nil)
	{
		printf("%d ",depth);
		return 1;
	}
	if (node->left != tree->nil && node != node->left->parent)
	{
		return 0;
	}
	if (node->right != tree->nil && node != node->right->parent)
	{
		return 0;
	}
	if (BLACK == node->color)
	{
		depth++;
	}
	check_node(tree,node->left,depth);
	check_node(tree,node->right,depth);
	return 1;
}
char check(rb_tree *tree)
{
	//2
	if (RED == tree->root->color)
	{
		return 0;
	}
	//3
	if (RED == tree->nil->color)
	{
		return 0;
	}
	//4,5
	check_node(tree,tree->root,0);
	printf("\n");
	return 1;
}